package leetcode.editor.cn;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
  * 题目Id：105
  * 题目：从前序与中序遍历序列构造二叉树
  * 日期：2024-03-15 18:19:56
*/
//给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并
//返回其根节点。
//
//
//
// 示例 1:
//
//
//输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
//输出: [3,9,20,null,null,15,7]
//
//
// 示例 2:
//
//
//输入: preorder = [-1], inorder = [-1]
//输出: [-1]
//
//
//
//
// 提示:
//
//
// 1 <= preorder.length <= 3000
// inorder.length == preorder.length
// -3000 <= preorder[i], inorder[i] <= 3000
// preorder 和 inorder 均 无重复 元素
// inorder 均出现在 preorder
// preorder 保证 为二叉树的前序遍历序列
// inorder 保证 为二叉树的中序遍历序列
//
//
// Related Topics 树 数组 哈希表 分治 二叉树 👍 2262 👎 0


public class ConstructBinaryTreeFromPreorderAndInorderTraversal {
    // 辅助方法：打印二叉树（层序遍历）
    public static void printTree(TreeNode root) {
        if (root == null) return;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                System.out.print(node.val + " ");
                queue.offer(node.left);
                queue.offer(node.right);
            } else {
                System.out.print("null ");
            }
        }
    }
    public static void main(String[] args) {
        Solution solution = new ConstructBinaryTreeFromPreorderAndInorderTraversal().new Solution();

        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};

        TreeNode root = solution.buildTree(preorder, inorder);

        // 输出构造的二叉树（可以根据需要实现一个打印树的辅助方法）
        printTree(root);
    }
    //leetcode submit region begin(Prohibit modification and deletion)

//Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

    /**
     * 前序和中序遍历构造二叉树
     */

class Solution {
    private Map<Integer, Integer> indexMap;

        public TreeNode buildTree(int[] preorder, int[] inorder) {
            // 用 HashMap 存储中序遍历元素的索引，避免重复查找
            Map<Integer, Integer> inorderMap = new HashMap<>();
            for (int i = 0; i < inorder.length; i++) {
                inorderMap.put(inorder[i], i);
            }

            // 从前序和中序遍历中构建二叉树
            return buildTreeHelper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inorderMap);
        }

        /**
         *
         * @param preorder 前序遍历数组
         * @param preStart 前序遍历第一个节点
         * @param preEnd 前序遍历最后一个节点
         * @param inorder 中序遍历数组
         * @param inStart 中序遍历第一个节点
         * @param inEnd 中序遍历最后一个节点
         * @param inorderMap  中序遍历元素和索引的映射
         * @return
         */
        private TreeNode buildTreeHelper(int[] preorder, int preStart, int preEnd,
                                         int[] inorder, int inStart, int inEnd,
                                         Map<Integer, Integer> inorderMap) {
            if (preStart > preEnd || inStart > inEnd) {
                return null;
            }

            // 前序遍历的第一个元素是根节点
            int rootVal = preorder[preStart];
            TreeNode root = new TreeNode(rootVal);

            // 根节点在中序遍历中的位置
            int rootIndexInInorder = inorderMap.get(rootVal);

            // 左子树的元素个数
            int leftTreeSize = rootIndexInInorder - inStart;

            // 递归构造左子树和右子树
            root.left = buildTreeHelper(preorder, preStart + 1, preStart + leftTreeSize,
                    inorder, inStart, rootIndexInInorder - 1,
                    inorderMap);
            root.right = buildTreeHelper(preorder, preStart + leftTreeSize + 1, preEnd,
                    inorder, rootIndexInInorder + 1, inEnd,
                    inorderMap);

            return root;
        }


        /**
         * 构造二叉树:
         * 1.前序遍历的第一个节点，就是构造二叉树的根节点
         *
         * @param preorder
         * @param root
         * @param preorder_right
         * @param inorder_left   这个参数的作用就是知道方便以后知道左子树的节点的数量
         * @return
         */
    public TreeNode myBuildTree2(int[] preorder,   int root, int preorder_right, int inorder_left) {
        // 递归的结束条件

        //在中序遍历里面找打根节点
        Integer i = indexMap.get(preorder[root]);//中序遍历根节点的下标
        //左子树起始点的下标




        //右子树末点的下表




        return  null;
    }


}

//leetcode submit region end(Prohibit modification and deletion)

}
